package interviewClassic150;

import org.junit.Test;

public class ReverseWords {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        //先消除额外空格
        int insertInd = 0;
        int i = 0;
        while (i < chars.length) {
            if (chars[i] != ' ') {
                //字母，填入
                chars[insertInd++] = chars[i++];
            } else if (i > 0 && chars[i - 1] != ' ') {
                //字母后的第一个空格，填入
                chars[insertInd++] = chars[i++];
            } else {
                //多出来的空格
                i++;
            }
        }
        //存在后置空格的情况
        if (chars[insertInd - 1] == ' ') insertInd--;
        //现将当前字符串翻转，然后再将每个单词翻转
        reverse(chars,0,insertInd);
        //每个单词翻转
        int start = 0;
        for (int j = 0; j < insertInd; j++) {
            if (chars[j] == ' ') {
                reverse(chars,start,j);
                start = j + 1;
            }
        }
        //最后一个单词的翻转
        reverse(chars,start,insertInd);
        //返回字符串
        return new String(chars,0,insertInd);
    }

    public void reverse(char[] chars, int start, int end) {
        int left = start;
        int right = end - 1;
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }

    @Test
    public void test() {
        String str = "  hello world  ";
        String s = reverseWords(str);
        System.out.println(s);
    }
}
